package com.example.design.leetcode.arrayAndString;

//剑指 Offer 53 - I. 在排序数组中查找数字 I - 解决方案
//题目描述
//        统计一个数字在排序数组中出现的次数
//
//        示例 1:
//
//        输入: nums = [5,7,7,8,8,10], target = 8
//        输出: 2
//        示例 2:
//
//        输入: nums = [5,7,7,8,8,10], target = 6
//        输出: 0
//        限制：
//
//        0 <= 数组长度 <= 50000
//        nums 是一个非递减数组

// 标签：二分


//先找出taget最右边的索引，再找出target-1最右边的索引，相减就是target的数
public class Practice09 {

    public int search(int[] nums, int target) {
        return a(nums, target) - a(nums, target-1) ;
    }

    public int a(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            // target在mid右边
            if (nums[mid] <= target) {
                left = mid + 1;

            } else {
                right = mid -1;
            }
        }
        return left;
    }


}
